/**
 * MaxDiffBetweenTwoNumber.java created by zhangzhidong 
 * at 下午9:48:34 2015年10月6日
 */
package newcoder.algorithm;

/**
 * @author zhangzhidong
 *
 */
public class MaxDiffBetweenTwoNumber {

	/**
	 * 
	 * 
	 * 【题目】
给定一个整型数组arr，返回如果排序之后，相邻两数的最大差值。 
【举例】
arr=[9,3,1,10]。如果排序，结果为[1,3,9,10]，9和3的差为最大差值，故返回6。
arr=[5,5,5,5]。返回0。
【要求】
如果arr的长度为N，请做到时间复杂度为O(N)。
	 * 下午9:48:35 2015年10月6日
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		algorithm(new int []{1,3,9,10});
		
	}
	public static int algorithm(int arr[]){
		int polar[] = findMaxMinAndStore(arr);
		if(polar[0]==polar[1]){
			return 0;
		}
		int num=arr.length;
		boolean isHasNum[] = new boolean [num+1];
		int largestNum[] = new int[num+1];
		int smallestNum[] = new int[num+1];
		for(int i=0;i<largestNum.length;i++){
			largestNum[i]=Integer.MIN_VALUE;
			smallestNum[i]=Integer.MAX_VALUE;
		}
		int diff=polar[1]-polar[0];
		int slot = diff / num;
		isHasNum[0]=isHasNum[num]=true;
		largestNum[num]=polar[1];
		smallestNum[0]=polar[0];
		for(int i =0;i<arr.length;i++){
			int index=(arr[i]-polar[0]) / slot;
			isHasNum[index]=true;
			if(arr[i]>largestNum[index]) largestNum[index]=arr[i];
			else if(arr[i]<smallestNum[index]) smallestNum[index]=arr[i];
		}
		int mostdiff=0;
		 int flag1=smallestNum[0];
		for(int i=0;i<num-1;i++){
	
			if(isHasNum[i]){
				mostdiff=largestNum[i]-flag1;
			}else{
				
			}
		}
		System.out.println(mostdiff);
		return 0;
		
		
		
	}
	public static int [] findMaxMinAndStore(int num[]){
		int max=0;
		int min=0;	
		max=min=num[0];
		for(int i =1;i<num.length;i++){
			if(num[i]>max){
				max=num[i];
			}else if(num[i]<min){
				min=num[i];
			}
		}
		return new int[]{min,max};
		
	}
	

}
